package leetcode.code1319;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
	public int makeConnected(int n, int[][] connections) {
		int lineSize = connections.length;
		if (lineSize + 1 < n) {
			return -1;
		}
		List<Set<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new HashSet<>());
		}
		for (int i = 0; i < connections.length; i++) {
			int a = connections[i][0], b = connections[i][1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		boolean[] net = new boolean[n];
		int netSize = 0;
		for (int i = 0; i < n; i++) {
			if (!net[i]) {
				this.f(net, i, nexts);
				netSize++;
			}
		}
		return netSize - 1;
	}

	private void f(boolean[] net, int i, List<Set<Integer>> nexts) {
		if (net[i]) {
			return;
		}
		net[i] = true;
		Set<Integer> next = nexts.get(i);
		for (int nxt : next) {
			this.f(net, nxt, nexts);
		}
	}
}
